UVa/11590 - Prefix lookup/11590.7.cpp

   1 /*
   2   Experimenting wiht the input...
   3
   4   Accepted too.
   5  */
   6 #include <iostream>
   7 #include <map>
   8 #include <cstdio>
   9 #include <cstring>
  10 #include <cassert>
  11
  12 using namespace std;
  13
  14 const int BUFSIZE = 512;
  15 char buf[BUFSIZE];
  16
  17 #define D(x) cout << #x " is " << (x) << endl
  18
  19 typedef unsigned long long uint64;
  20
  21 struct node{
  22   bool end;
  23   node * left;
  24   node * right;
  25   node(bool end) : end(end) {
  26     left = right = NULL;
  27   }
  28   node * getLeft(){
  29     if (left == NULL) left = new node(false);
  30     return left;
  31   }
  32   node * getRight(){
  33     if (right == NULL) right = new node(false);
  34     return right;
  35   }
  36 };
  37
  38 //returns 2^e
  39 inline uint64 pow2(int e){
  40   if (e == 64) return 0;
  41   return uint64(1) << e;
  42 }
  43
  44 void clean(node * cur){
  45   if (cur == NULL) return;
  46   clean(cur->left);
  47   clean(cur->right);
  48   delete cur;
  49 }
  50
  51 int n, m;
  52
  53 /*
  54   Returns how many strings were counted under the tree rooted at cur, including it.
  55 */
  56 uint64 alreadyCounted(node * cur, int depth = 0){
  57   if (cur == NULL) return 0;
  58   uint64 left = alreadyCounted(cur->left, depth + 1);
  59   uint64 right = alreadyCounted(cur->right, depth + 1);
  60   uint64 ret = left + right;
  61   if (cur->end){
  62     //count strings matched to this one
  63     ret += pow2(m - depth) - left - right;
  64   }
  65   return ret;
  66 }
  67
  68
  69 int main(){
  70   while (true){
  71     scanf("%d%d\n", &n, &m);
  72     if (n == 0 && m == 0) break;
  73     node * root = new node(true);
  74     for (int i=0; i<n; ++i){
  75       scanf("%s", buf);
  76       node * cur = root;
  77       for (int j=0; ; ++j){
  78         if (buf[j] == '*'){
  79           cur->end = true;
  80           break;
  81         }
  82         node * next;
  83         if (buf[j] == '0'){
  84           next = cur->getLeft();
  85         }else if (buf[j] == '1'){
  86           next = cur->getRight();
  87         }else{
  88           printf("Bad character %c at query %d, position %d\n", buf[j], i, j);
  89           //assert(false);
  90         }
  91         cur = next;
  92       }
  93     }
  94     int k;
  95     scanf("%d\n", &k);
  96     for (int i=0; i<k; ++i){
  97       scanf("%s", buf);
  98       node * cur = root;
  99       for  (int j=0; buf[j] != '*'; ++j){
 100         if (buf[j] == '0'){
 101           cur = cur->left;
 102         }else if (buf[j] == '1'){
 103           cur = cur->right;
 104         }
 105       }
 106       string s(buf);
 107       s = s.substr(0, s.size()-1);
 108
 109       uint64 ans = pow2(m - s.size())
 110         - alreadyCounted(cur->left, s.size()+1) - alreadyCounted(cur->right, s.size()+1);
 111       printf("%llu\n", ans);
 112     }
 113     printf("\n");
 114     clean(root);
 115   }
 116   return 0;
 117 }